// hash_map standard header -*-c++-*-
// Copyright 2003-2010 IAR Systems AB. 
#ifndef _HASH_MAP_
#define _HASH_MAP_

#ifndef _SYSTEM_BUILD
#pragma system_include
#endif

#include <xhash>
_STD_BEGIN

#pragma language = save
#pragma language = extended
// TEMPLATE CLASS _Hmap_traits
template<class _Kty,    // key type
         class _Ty,      // mapped type
         class _Tr,      // comparator predicate type
         class _Alloc,   // actual allocator type (should be value allocator)
         bool _Mfl>      // true if multiple equivalent keys are permitted
class __memory_of(_Kty) _Hmap_traits
{       // traits required to make _Hash behave like a map
public:
  typedef _Kty key_type;
  typedef pair<const _Kty, _Ty> value_type;
  typedef _Tr key_compare;
  typedef typename _Alloc::template rebind<value_type>::other
    allocator_type;
  enum
  {       // make multi parameter visible as an enum constant
    _Multi = _Mfl
  };

  _Hmap_traits()
    : _Kcmp()
  {}      // construct with default comparator

  _Hmap_traits(const _Tr& _Traits)
    : _Kcmp(_Traits)
  {}      // construct with specified comparator

  class value_compare
    : public binary_function<value_type, value_type, bool>
   {       // functor for comparing two element values
     friend class _Hmap_traits<_Kty, _Ty, _Tr, _Alloc, _Mfl>;

   public:
     bool operator()(const value_type& _Left,
                     const value_type& _Right) const
     {       // test if _Left precedes _Right by comparing just keys
       return (comp(_Left.first, _Right.first)); 
     }
     
     value_compare(const key_compare& _Traits)
       : comp(_Traits)
     {}      // construct with specified predicate

   protected:
     key_compare comp;       // the comparator predicate for keys
   };

  static const _Kty& _Kfn(const value_type& _Val)
  {       // extract key from element value
    return (_Val.first); 
  }

  _ClassUtil::_MemHolder<value_type, _Tr>
                              _Kcmp;       // the comparator predicate for keys

  key_compare   comp() const { return _Kcmp; }
  key_compare & comp()       { return _Kcmp; }
};

// TEMPLATE CLASS hash_map
template<class _Kty,
         class _Ty,
         class _Tr = hash_compare<_Kty, less<_Kty> >,
         class _Alloc = allocator<pair<const _Kty, _Ty> > >
class hash_map
: public _Hash<_Hmap_traits<_Kty, _Ty, _Tr, _Alloc, false> >
{       // hash table of {key, mapped} values, unique keys
public:
  typedef _Hash<_Hmap_traits<_Kty, _Ty, _Tr, _Alloc, false> > _Mybase;
  typedef _Kty key_type;
  typedef _Ty mapped_type;
  typedef _Ty referent_type;
  typedef _Tr key_compare;
  typedef typename _Mybase::value_compare value_compare;
  typedef typename _Mybase::allocator_type allocator_type;
  typedef typename _Mybase::size_type size_type;
  typedef typename _Mybase::difference_type difference_type;
  typedef typename _Mybase::pointer pointer;
  typedef typename _Mybase::const_pointer const_pointer;
  typedef typename _Mybase::reference reference;
  typedef typename _Mybase::const_reference const_reference;
  typedef typename _Mybase::iterator iterator;
  typedef typename _Mybase::const_iterator const_iterator;
  typedef typename _Mybase::reverse_iterator reverse_iterator;
  typedef typename _Mybase::const_reverse_iterator
  const_reverse_iterator;
  typedef typename _Mybase::value_type value_type;

  hash_map()
  : _Mybase(key_compare(), allocator_type())
  {}      // construct empty map from defaults

  explicit hash_map(const key_compare& _Traits)
  : _Mybase(_Traits, allocator_type())
  {}      // construct empty map from comparator

  hash_map(const key_compare& _Traits, const allocator_type& _Al)
  : _Mybase(_Traits, _Al)
  {}      // construct empty map from comparator and allocator

  template<class _Iter>
  hash_map(_Iter _First, _Iter _Last)
  : _Mybase(key_compare(), allocator_type())
  {       // construct map from sequence, defaults
    for (; _First != _Last; ++_First)
    this->insert(*_First); 
  }

  template<class _Iter>
  hash_map(_Iter _First, _Iter _Last, const key_compare& _Traits)
  : _Mybase(_Traits, allocator_type())
  {       // construct map from sequence, comparator
    for (; _First != _Last; ++_First)
    this->insert(*_First); 
  }

  template<class _Iter>
  hash_map(_Iter _First, _Iter _Last, const key_compare& _Traits,
           const allocator_type& _Al)
  : _Mybase(_Traits, _Al)
  {       // construct map from sequence, comparator, and allocator
    for (; _First != _Last; ++_First)
    this->insert(*_First); 
  }

  mapped_type& operator[](const key_type& _Keyval)
  {       // find element matching _Keyval or insert with default mapped
    typename _ClassUtil::_TmpHolder<value_type>::_Type
                            _Val(_Keyval); // mapped_type is default constructed
    iterator _Where = this->insert(_Val).first;
    return ((*_Where).second); 
  }
};

// TEMPLATE CLASS hash_multimap
template<class _Kty,
         class _Ty,
         class _Tr = hash_compare<_Kty, less<_Kty> >,
         class _Alloc = allocator<pair<const _Kty, _Ty> > >
class hash_multimap
: public _Hash<_Hmap_traits<_Kty, _Ty, _Tr, _Alloc, true> >
{       // hash table of {key, mapped} values, non-unique keys
public:
  typedef _Hash<_Hmap_traits<_Kty, _Ty, _Tr, _Alloc, true> > _Mybase;
  typedef _Kty key_type;
  typedef _Ty mapped_type;
  typedef _Ty referent_type;      // old name, magically gone
  typedef _Tr key_compare;
  typedef typename _Mybase::value_compare value_compare;
  typedef typename _Mybase::allocator_type allocator_type;
  typedef typename _Mybase::size_type size_type;
  typedef typename _Mybase::difference_type difference_type;
  typedef typename _Mybase::pointer pointer;
  typedef typename _Mybase::const_pointer const_pointer;
  typedef typename _Mybase::reference reference;
  typedef typename _Mybase::const_reference const_reference;
  typedef typename _Mybase::iterator iterator;
  typedef typename _Mybase::const_iterator const_iterator;
  typedef typename _Mybase::reverse_iterator reverse_iterator;
  typedef typename _Mybase::const_reverse_iterator
  const_reverse_iterator;
  typedef typename _Mybase::value_type value_type;

  hash_multimap()
  : _Mybase(key_compare(), allocator_type())
  {}      // construct empty map from defaults

  explicit hash_multimap(const key_compare& _Traits)
  : _Mybase(_Traits, allocator_type())
  {}      // construct empty map from comparator

  hash_multimap(const key_compare& _Traits,
                const allocator_type& _Al)
  : _Mybase(_Traits, _Al)
  {}      // construct empty map from comparator and allocator

  template<class _Iter>
  hash_multimap(_Iter _First, _Iter _Last)
  : _Mybase(key_compare(), allocator_type())
  {       // construct map from sequence, defaults
    _Mybase::insert(_First, _Last);
  }

  template<class _Iter>
  hash_multimap(_Iter _First, _Iter _Last, const key_compare& _Traits)
  : _Mybase(_Traits, allocator_type())
  {       // construct map from sequence, comparator
    _Mybase::insert(_First, _Last);
  }

  template<class _Iter>
  hash_multimap(_Iter _First, _Iter _Last, const key_compare& _Traits,
                const allocator_type& _Al)
  : _Mybase(_Traits, _Al)
  {       // construct map from sequence, comparator, and allocator
    _Mybase::insert(_First, _Last);
  }

  iterator insert(const value_type& _Val)
  {       // insert a {key, mapped} value
    return (_Mybase::insert(_Val).first); 
  }

  iterator insert(iterator _Where, const value_type& _Val)
  {       // insert a {key, mapped} value, with hint
    return (_Mybase::insert(_Where, _Val)); 
  }

  template<class _Iter>
  _ALLOW_ONLY_ITERATORS(_Iter, void)
  insert(_Iter _First, _Iter _Last)
  {
    _Mybase::insert(_First, _Last);
  }
};
#pragma language = restore
_STD_END
#endif /* _HASH_MAP_ */

/*
 * Copyright (c) 1992-2009 by P.J. Plauger.  ALL RIGHTS RESERVED.
 * Consult your license regarding permissions and restrictions.
 V5.04:0576 */
